/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.subcommands;

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

import mosdi.fa.AutomataUtils;
import mosdi.fa.FiniteMemoryTextModel;
import mosdi.fa.IIDTextModel;
import mosdi.fa.MarkovianTextModel;
import mosdi.matching.Matcher;
import mosdi.paa.MinimizedDAA;
import mosdi.paa.PAA;
import mosdi.paa.TextBasedPAA;
import mosdi.paa.apps.PatternMatchingDAA;
import mosdi.paa.apps.PatternMatchingDAAAlternative;
import mosdi.tools.PatternMatchingAnalysis;
import mosdi.util.Alphabet;
import mosdi.util.BitArray;
import mosdi.util.Log;
import mosdi.util.iterators.LexicographicalIterator;
import mosdi.util.iterators.RangeIterator;
import mosdi.util.iterators.StringIterator;

public class AutomataSizesSubcommand extends Subcommand {

	@Override
	public String description() {
		return "Returns automata sizes for all patterns of given length.";
	}

	@Override
	public String usage() {
		return super.usage()+" [options] <algorithm> <pattern-length>\n" +
		"\n" +
		"Iterates over all patterns of given length and returns for each pattern\n" +
		"the size of the automaton needed to simulate the given algorithm.\n" +
		"\n" +
		"If two algorithms are given (comma-separated), the product automaton\n" +
		"is constructed.\n" +
		"\n" +
		"Possible algorithms: "+ PatternMatchingAnalysis.allMatcherNames() +"\n" +
		"\n" +
		"Options:\n" +
		"  -O <order>: order of text model (default: 0)\n" +
		"  -A <alphabet>: default: ACGT\n" +
		"  -a: also construct alternative DAA (smaller state space, larger value space)\n" +
		"  -m <maxCost>: maximal cost to be considered; affects size of PAA (default: 99)\n" +
		"  -l <lower>: lexicographically smallest pattern to be processed\n" +
		"  -u <upper>: lexicographically largest pattern to be processed";
	}

	@Override
	public String name() {
		return "automata-sizes";
	}

	@Override
	public int run(String[] args) {
		parseOptions(args, 2, "O:am:l:u:A:");

		// Option dependencies
		// -- none --

		// Mandatory arguments
		String algorithmParameter = getStringArgument(0);
		int patternLength = getIntArgument(1);

		// Options
		int modelOrder = getNonNegativeIntOption("O", 0);
		boolean constructAlternativeDAA = getBooleanOption("a", false);
		int maxCost = getNonNegativeIntOption("m", 99);
		Alphabet alphabet = Alphabet.getDnaAlphabet();
		if (optionSet.has("A")) alphabet = new Alphabet((String)optionSet.valueOf("A"));
		int[] lower = null;
		int[] upper = null;
		if (optionSet.has("l")) {
			lower = alphabet.buildIndexArray((String)optionSet.valueOf("l"));
			if (lower.length!=patternLength) {
				Log.errorln("Argument to option -l: must have length "+patternLength);
				System.exit(1);
			}
		}
		if (optionSet.has("u")) {
			upper = alphabet.buildIndexArray((String)optionSet.valueOf("u"));
			if (upper.length!=patternLength) {
				Log.errorln("Argument to option -u: must have length "+patternLength);
				System.exit(1);
			}
			upper[upper.length-1]+=1;
		}
		
		List<String> algorithmNames = new ArrayList<String>();
		StringTokenizer st = new StringTokenizer(algorithmParameter,",",false);
		while (st.hasMoreTokens()) algorithmNames.add(st.nextToken());
		if (algorithmNames.size()!=1) {
			Log.errorln("Error: #algorithm!=1. Not yet implemented.");
			return 1;
		}
		FiniteMemoryTextModel textModel = null;
		if (modelOrder==0) textModel = new IIDTextModel(alphabet.size());
		else {
			double[] qGramCounts = new double[(int)Math.pow(alphabet.size(), modelOrder+1)];
			for (int j=0; j<qGramCounts.length; ++j) {
				qGramCounts[j] = 1.0 + ((double)j)/qGramCounts.length;
			}
			textModel = new MarkovianTextModel(modelOrder, alphabet.size(), qGramCounts);
		}

		LexicographicalIterator iterator = new StringIterator(alphabet.size(), patternLength);
		if ((lower!=null) || (upper!=null)) {
			iterator = new RangeIterator(iterator, lower, upper);
		}
		Log.println(Log.Level.STANDARD, "Format: >> pattern #daa-states #daa-state-classes #daa-states-minimized #paa-states #paa-states*#paa-values");
		while (iterator.hasNext()) {
			int[] pattern = iterator.next();
			Matcher matcher = PatternMatchingAnalysis.getMatcher(algorithmNames.get(0), alphabet.size(), pattern);
			if (matcher==null) {
				Log.errorln("Error: unknown algorithm: "+algorithmNames.get(0)+".");
				return 1;
			}
			PatternMatchingDAA daa = new PatternMatchingDAA(matcher.costScheme(), maxCost);;
			MinimizedDAA minimizedDaa = new MinimizedDAA(daa);
			PAA paa = new TextBasedPAA(minimizedDaa, textModel);
			Log.printf(Log.Level.STANDARD, ">> %s %d %d %d %d %d", alphabet.buildString(pattern), daa.getStateCount(), daa.getStatePartition().blockCount(), minimizedDaa.getStateCount(), paa.getStateCount(), paa.getStateCount()*paa.getValueCount());
			PatternMatchingDAAAlternative altDaa = null;
			MinimizedDAA altMinimizedDaa = null;
			PAA altPaa = null;
			if (constructAlternativeDAA) {
				altDaa = new PatternMatchingDAAAlternative(matcher.costScheme(), maxCost);
				altMinimizedDaa = new MinimizedDAA(altDaa);
				altPaa = new TextBasedPAA(altMinimizedDaa, textModel);
				Log.printf(Log.Level.STANDARD, " >alternative> %d %d %d %d %d", altDaa.getStateCount(), altDaa.getStatePartition().blockCount(), altMinimizedDaa.getStateCount(), altPaa.getStateCount(), altPaa.getStateCount()*altPaa.getValueCount());
			}
			Log.printf(Log.Level.STANDARD, "\n");
			if (Log.levelAtLeast(Log.Level.DEBUG)) {
				Log.printf(Log.Level.DEBUG, "  Minimized DAA for %s:\n", alphabet.buildString(pattern));
				BitArray reachability = AutomataUtils.findReachableStates(minimizedDaa);
				for (int state=0; state<minimizedDaa.getStateCount(); ++state) {
					int emission = minimizedDaa.getEmission(state);
					Log.printf(Log.Level.DEBUG, " %c%c State %d (cost: %d, transitions:", reachability.get(state)?' ':'U', state==minimizedDaa.getStartState()?'S':' ', state, emission);
					for (int c=0; c<alphabet.size(); ++c) {
						Log.printf(Log.Level.DEBUG, " %c:%d",alphabet.get(c),minimizedDaa.getTransitionTarget(state, c));
					}
					Log.printf(Log.Level.DEBUG, "):");
					for (int originalState : minimizedDaa.getEquivalencePartition().block(state)) {
						int[] window = daa.decodeStateToWindow(originalState);
						int pos = daa.decodeStateToPosition(originalState);
						Log.printf(Log.Level.DEBUG, " %s/%d", alphabet.buildString(window), pos);
					}
					Log.printf(Log.Level.DEBUG, "\n");
				}
				if (constructAlternativeDAA) {
					Log.printf(Log.Level.DEBUG, "  Alternative minimized DAA for %s:\n", alphabet.buildString(pattern));
					BitArray altReachability = AutomataUtils.findReachableStates(altMinimizedDaa);
					for (int state=0; state<altMinimizedDaa.getStateCount(); ++state) {
						int emission = altMinimizedDaa.getEmission(state);
						Log.printf(Log.Level.DEBUG, " %c%c State %d (shift: %d, cost: %d, transitions:", altReachability.get(state)?' ':'U', state==altMinimizedDaa.getStartState()?'S':' ', state, altDaa.decodeEmissionToShift(emission), altDaa.decodeEmissionToCost(emission));
						for (int c=0; c<alphabet.size(); ++c) {
							Log.printf(Log.Level.DEBUG, " %c:%d",alphabet.get(c),altMinimizedDaa.getTransitionTarget(state, c));
						}
						Log.printf(Log.Level.DEBUG, "):");
						for (int originalState : altMinimizedDaa.getEquivalencePartition().block(state)) {
							Log.printf(Log.Level.DEBUG, " %s", alphabet.buildString(altDaa.decodeState(originalState)));
						}
						Log.printf(Log.Level.DEBUG, "\n");
					}
				}
			}
		}
		
		return 0;
	}

}
